Existing methods of displaying tree-like structures on a video screen fall in one of two general categories. The first method involves the use of successively detailed outlines. At the top level, for example, a display might consist of a list of three similarly indented items. The first, then, might be further refined into subitems. These subitems might be indented, for example, or differently colored. These, in turn, could be further refined.
In general, standard outlining methods of this sort have been used in "idea processors," like ThinkTank.TM. from Living Videotext. They also have been used in slightly modified form to display hierarchical structures in computer source code. Brackets, for example, are used to set off successive structures (refinements) in "Action Diagrams" (e.g., Martin & McClure, 1985). These outlining methods help to focus human perception. This latter quality is extremely important since it provides at a glance crucial structural information that would otherwise have to be inferred from detailed study.
The techniques used, however, are inherently data-based. Systems designs and source code, on the other hand, invariably involve processes as well as data structures. As Dijkstra (1972) has shown, there are three major types of process decomposition: sequence, selection and iteration or loop, plus their variations. Current outlining methods do not provide a visual or graphical distinction between different types of structural decompositions.
The second general method involves the use of windows on computer screens and has a relatively recent history. Initially, windows were used to superimpose new information (e.g., a submenu of choices) on an existing background screen. This idea has been extended more systematically in what are commonly called "smalltalk" or "object-oriented" systems. A typical object-oriented interface uses a series of overlapping windows, with the `top` fully visible window constituting the current workfile (see D. Robson, 1981, and L. Tesler, 1981). The underlying metaphor is that of a table top. A sample configuration of overlapping windows is shown in FIG. 1.
Overlapping windows also are widely used in Computer Aided Systems (CAS) software and in terms of its more specific variants: Computer Aided Design (CAD), Computer Aided Manufacturing (CAM), Computer Aided Engineering (CAE) and Computer Aided Software Engineering (CASE) systems. Such windows are equally useful in representing both hierarchical data structures and procedures.
The representation of relationships among various entities plays an important role in each of these areas. Typically, entities are represented by simple objects (boxes, circles, etc, which are often labeled), and by directed lines connecting these entities. FIG. 2 is illustrative. Franke et al have developed a method for generating and displaying limited portions of tree structures in a limited display area (see U.S. Pat. No. 4,710,763). This method is concerned with displaying trees at some predetermined level of refinement (together with the associated parent and successor nodes). The overall higher level structure, however, is still displayed in a separate window.
In computer aided systems design, it is often essential to refine individual elements in a display, tree-like or otherwise (e.g., FIG. 2). Such refinement involves expansion of one (or more) of the elements to show the elements and relationships of which it is composed. This is normally done in a separate window. Components in an expansion may be expanded in turn. In principle, the process may be repeated indefinitely.
Existing processes for positioning windows involve overlapping rectangular windows (e.g., as shown above in FIG. 1). Typically, windows also can be moved arbitrarily on the screen either by use of a "mouse" or from the keyboard (see U.S. Pat. No. 4,464,652).
Apple Computer, Inc. has since refined the process further for use on its Macintosh computers by using techniques which permit the representation and manipulation of any arbitrarily defined regions in terms of inversion points (see U.S. Pat. No. 4,622,545). These techniques are potentially useful in dealing with arbitrary shapes in bit mapped systems.
These methods of windowing have important limitations, however, when it comes to representing different levels of refinement in displaying hierarchical tree-like designs. First, since they typically require computer generated graphics, they are relatively slow and/or require high powered computer workstations to achieve acceptable levels of performance in environments where windows representing complex tree-like designs need to be changed frequently and/or quickly. The high memory and processing requirements of graphics based windowing systems also tend to restrict the number of levels of refinement.
Given the relatively rapid rate at which computer technology is advancing, these limitations may be considered temporary. Nonetheless, decrements in display times and the incremental costs for such hardware (over text based systems) are likely to remain for the foreseeable future. In short, a system based on the display of text characters would have advantages with regard to speed, and the size of computers on which windowing systems might be implemented. Display speed, for example, inherently depends on the sheer amount of video memory which must be updated for screen display, even though modern microcomputer hardware typically supports "direct writes" to screen memory. And, the amount of memory which must be updated in the case of bit mapped (graphic-based) system is greater than in character-based systems.
An even more serious (permanent) limitation of current representational and windowing processes is that it is not feasible to arrange windows so as to show relationships between different levels of refinement. That is, one can see relationships at any one level for those portions of a design that fit on the screen (e.g., see reference above to Franke et al). However, relationships at different levels of a refinement are spatially separate. Except in very special cases, it is effectively impossible to place expansions of a given entity on the screen in the same context in which the original entity appeared.
Suppose, for example, that one element (i.e., bubble) in the `window` of FIG. 2 is expanded to the next level of detail (e.g., a more refined data flow diagram). One way to display this expansion would be to decrease the size (increase the scale) of the expanded window so it would fit (essentially) inside the original bubble (element); in this case, unfortunately, the expansions become too small to see. The alternative is to increase the scale of the original window so the expression fits, but this results in less of the overall design being visible in the limited screen area. Consequently, expansions of elements in one window are typically displayed in a separate window.
To help compensate, existing methods use such techniques as darkening or otherwise marking entities which have been expanded. These techniques, however, do not help the eye perceive expanded details directly in the higher level contexts to which they logically belong. Experience (as well as cognitive research) shows that it is difficult to work effectively with more than three or four levels of refinement. It becomes increasingly difficult to know how the various levels of refinement are interrelated.
FLOWforms (Scandura, 1987) have some of the desired properties but it is not obvious how they map into various programming languages or how they might be constructed automatically in real time. The current invention uses FLOWforms to retain the contextual advantages of displaying windows using outlining methods along with the visual and procedural (process) capabilities of overlapping windows. In brief, this is accomplished by showing how various configurations of rectangular regions can be constructed and embedded within one another. Different levels of both data and process oriented designs are enclosed in simple box-like displays. In this context, it is important to recognize that items enclosed in simple shapes, such as rectangular boxes, help human perception as much as (and typically more than) using a variety of complex graphical shapes.
There are, of course, various means of representation which are based on straight lines (rather than arbitrary graphics). We mention the Nassi-Shneiderman representation since it is related to the FLOWform.TM. representation used in this invention. Unlike the use of arrows, as shown in FIG. 3a, b and c as in standard flowcharts, the corresponding Nassi-Shneiderman representations would look like FIG. 4a, b and c. One minor problem with the Nassi-Shneiderman format is the lack of any means of distinguishing different levels of a sequence refinement. By way of contrast FIG. 5a shows an alternative representation used in this invention in which A, B and C are all seen to be part of the same refinement of the sequence containing them, whereas FIG. 5b shows that A and B form one sequence which together with C form a higher level sequence.
A still more serious problem is that the Nassi-Shneiderman representation of a selection (FIG. 4b) splits the available screen horizontally. Consequently, refinement of B or C (in FIG. 4b) would split the screen still further. Very rapidly, one runs out of space for display purposes. A third limitation is equally critical in so far as the proposed process invention is concerned. The Nassi-Shneiderman format says nothing about the representation of relationships between different levels of refinement. This format is subject to the same limitations described above in so far as windowing is concerned.
A final consideration is that the Nassi-Shneiderman representation does not explicitly provide for data structures. Indeed, there is no uniform and universally accepted method for representing both data and process graphically.
A number of patents deal with similar issues but have only superficial relevance. Lane et al (see U.S. Pat. No. 4,873,623) describe an invention pertaining to three level dynamic menus which have nothing to do with displaying the structure of systems involving data structures and processes. Although Franke et al (see U.S. Pat. No. 4,710,763) are concerned with displaying system structure in a limited area, the method of display, the type of representation and their restriction to representing three levels of a tree are very different. Atkinson's invention (see U.S. Pat. No. 4,622,545) deals with the compression and manipulation of images. We do not use compression and we manipulate characters rather than bit maps per se. Konno (see U.S. Pat. No. 4,486,745) deals with the general issue of creating patterns from a smaller number of symbols. The current invention uses a very restricted set of symbols, line segments, to produce simple rectangular patterns in a very efficient manner. Bass et al (see U.S. Pat. No. 4,559,533) deals with moving images on a CRT screen by assigning image priorities. Our invention uses well known technologies to move portions of screen memory. Lapson et al (see U.S. Pat. No. 4,464,652) refers to a mouse controller for a screen cursor. Our invention has nothing to do with mouse controllers. How the cursor is actually moved is irrelevant. Torres (see U.S. Pat. No. 4,821,211) deals with menu hierarchies, ours with system structures. Heckel (see U.S. Pat. No. 4,763,308) is concerned with displaying selected portions of two or more records from different files on a display screen. Our invention is concerned with displaying arbitrary combinations of levels of tree-like structures, always from a single file.